The present invention relates generally to computer-implemented databases and, in particular, to an efficient, ordered, reduced-space representation of multi-dimensional data.
State of the art database management systems (DBMS""s), like the underlying data files out of which and on top of which they historically grew, continue to store and manipulate data in a manner that closely mirrors the users"" view of the data. Users typically think of data as a sequence of records (or xe2x80x9ctuplesxe2x80x9d), each logically composed of a fixed number of xe2x80x9cfieldsxe2x80x9d (or xe2x80x9cattributesxe2x80x9d) that contain specific content about the entity described by that record. This view is naturally represented by a logical table (or xe2x80x9crelationxe2x80x9d) structure (referred to herein as a xe2x80x9crecord-based tablexe2x80x9d), such as a rectilinear grid, in which the rows represent records and the columns represent fields.
The long-standing existence of record-based tables and their correspondence to a conventional user view, in the absence of generally recognized drawbacks, has led to their nearly universal acceptance as the major underlying internal representation of databases. Yet record-based tables contain key structural weaknesses including high levels of unorderedness and redundancy that have traditionally been regarded as unavoidable. For example, such tables can be sorted or grouped (i.e., the contiguous positioning of identical values) on at most one criterion (based upon column values or some function of either column values or multiple column values). This limitation renders essential database functions, such as querying and updating, on all criteria other than this privileged one awkward and overly resource-intensive.
The above deficiencies inhere in the fundamental properties of the record-based table structure, in particular, the requirement that the positioning of each field be made co-linear with all other fields in the same record. This arbitrary positioning of fields in record-based table structures excludes all other arrangements. It thus obscures natural and exploitable latent data relationships that are revealed by more ordered, condensed and efficient data arrangements. Moreover, the inability of record-based tables to effectively group or sort data leads to negative characteristics of state of the art DBMS""s such as unorderedness, redundancy, cumbersomeness, algorithmic inefficiencies and performance instabilities.
Database research provides palliatives for these problems, but fails to uncover and address their underlying cause (i.e., the reliance on record-based table structures). For example, the inability to represent a natural, multi-dimensional grouping within the confines of a record-based table structure has led to the creation of index-based data structures. These supplementary structures are inherently and often massively redundant, but they establish groupings and orderings that cannot be directly represented using a conventional table. Index-based structures typically grow to be overly lengthy, convoluted and are cumbersome to maintain, optimize and especially update. Examples of common indexes are b-trees, t-trees, star-indexes, and various bit maps.
Other supplementary structures developed in the prior art have different drawbacks. For example, hash tables can provide rapid querying of individual data items, but their lack of sort ordering render them unsuitable for range queries or for any other operation that requires returning data in a specific order.
The ability to maintain an ordered, non-redundant, multi-dimensional data set, using flexible sorting and/or grouping criteria, is extremely useful to database management. Sorted data makes rapid searching and updating possible via, for example, binary search algorithms and insertion sorts. Grouped data enables condensation that reduces space requirements and further increases the speed of, for example, searching and updating.
A system of data storage in which most or all columns of a data table can be stored in grouped and/or sorted order is thus extremely desirable. Previous studies have investigated xe2x80x9cfully inverted databases,xe2x80x9d which index each column through traditional methods, preserving all the inadequacies of records and indexes. Additionally, the bloated storage requirements necessary to accommodate complete indexing tend to make fully inverted databases impractical, especially, but not only, in main memory databases.
It is therefore an object of the present invention to provide a fully or partially ordered (e.g., grouped and/or sorted) database without the deficiencies characteristic of the prior art, as mentioned above.
Briefly, instead of structuring a database as a table in which each row is a record and each column contains the fields in the record, as in earlier databases, the present invention permutes or otherwise modifies the columns to provide an advantage in, for example, space usage and/or speed of access, such that the rows no longer necessarily correspond to individual records. For example, one such modification is to condense the column by eliminating redundant values (which reduces memory usage); another is sort-ordering the column, ensuring that value groups will always appear in some particular order (which can greatly reduce the time required to search a column for a particular value); still another is to both condense and sort a column. Other permutations and modifications with other advantages are also possible. The table of permuted/modified values is referred to herein as the xe2x80x9cvalue table.xe2x80x9d
Logically, though not necessarily physically, separate data structures provide the information needed to reconstruct the xe2x80x9crecordsxe2x80x9d in the database. In particular, they provide xe2x80x9cinstancexe2x80x9d and xe2x80x9cconnectivityxe2x80x9d information, where instance information identifies the instances of each value in the field that is in a record and connectivity information associates each instance with a specific instance of a value in at least one other field.
In one embodiment of the invention, both the instance and connectivity information is provided in a table, referred to herein as the xe2x80x9cinstance table.xe2x80x9d Each column in the instance table corresponds to an attribute of the records in the database and is associated with a column in the value table that contains the values for that attribute (and possibly other attributes). Each cell (row/column location) in the instance table has a position (in one embodiment of the invention, its row number) and an instance value (the contents of the cell). An associated cell in the associated column of the value table is derived from each instance cell""s position. Also, an associated instance cell in another column of the instance table that belongs to the same record is derived from each instance cell""s instance value. Thus, in this embodiment, an instance cell""s position identifies the value which the cell is an instance of and an instance cell""s contents provides the connectivity information associating the instance with another instance cell in another field. A record can then be reconstructed starting at a cell in the instance table by deriving, from the cell""s position, the associated value cell in the value table and, from the cell""s instance value, the position of the associated instance cell, and repeating this process at the associated instance cell and so forth, with a last cell in the chain providing, in one embodiment, the corresponding position of the starting cell.
If a column of the value table is sorted but not condensed, the value table column and the associated column in the instance table has, in one embodiment of the invention, the same number of rows. An instance cell""s associated value cell is, in this one embodiment, the value cell in the associated value table column having the same row number as the instance cell. An instance cell""s associated instance cell (i.e., cell in another column of the instance table belonging to the same record) is the cell in a specified column having the row number given by the instance cell""s instance value. In one embodiment, the specified column is the next column in the instance table, with the last column referring back to the first column. For example, if column 1 of the value table is uncondensed and, after permutation, column 1, row 2 and column 2, row 5 of the value table belong to the same record and an instance of column 2, row 5 is at column 2, row 5 of the instance table, the instance table at column 1, row 2 would contain the number 5 (indicating that row 5 of the next column belongs to the same record).
If a value table column is condensed, there is in general no longer a one-to-one correspondence between that column and an instance table column that is associated with it. In this case, a table, referred to herein as a xe2x80x9cdisplacement table,xe2x80x9d is provided that, in one embodiment of the invention, has a column for each instance table column associated with a condensed value table column and specifies the range of instance table row numbers associated with each row of the value table column. The value cell associated with an instance cell is then determined by the corresponding displacement table column based on the instance cell""s position (row number). In one embodiment, a displacement table column has the same number of rows as an associated value table column with each cell in the displacement table providing the first row number in the range of instance table row numbers associated with the corresponding value cell. Alternatively, each cell in the displacement table could, for example, provide the last row number in the range of instance table row numbers, the total number of rows in the range, or some other value from which it is possible to derive the range of instance table row numbers associated with each value cell (i.e., the instances of each value).
One drawback of the displacement table, as just described, is that searching the displacement table for the value cell corresponding to an instance cell slows record reconstruction. This drawback is addressed in still another embodiment of the invention in which the instance value of an instance cell whose associated instance cell is in a column having a displacement column is set to the position of the value cell associated with the associated instance cell (as opposed to the position of the associated instance cell itself, as in the embodiment described above). The value of the associated instance cell is then directly obtainable without a search of the displacement table. In this embodiment, a table, referred to herein as an xe2x80x9coccurrence table,xe2x80x9d provides information for determining the associated instance cell.
In one embodiment of the occurrence table, each column in the instance table that has cells with instance values as just described has an associated column in the occurrence table that has the same number of rows. A cell in the occurrence table is associated with a cell in the instance table based, in this embodiment, on its position and specifies an offset. The offset is added to the first row number in the range of instance table row numbers associated with the value cell to arrive at the associated instance cell. The first row number is derived from the displacement table based on the instance value of the instance cell. The connectivity information for an instance cell is thus provided in this embodiment by the instance cell""s contents, the occurrence table and the displacement table.
The data structures described herein may be, but need not be, entirely in RAM or distributed across a network comprised of a multiplicity of data processors. They may also be implemented in a variety of ways and the invention herein is in no way limited to the examples given of particular implementations. For example, one embodiment may involve only partly storing the data set using the computer-implemented database and methods described herein, with the remainder stored using traditional table-based methods. Information may be stored in various formats and the invention is not limited to any particular format. The contents of particular columns may be represented by functions or by functions in combination with other stored information or by stored information in any form, including bitmaps.
More generally, while the value, instance, displacement and occurrence tables have been described as xe2x80x9ctablesxe2x80x9d having rows, columns and cells, the invention is not limited to such structures. Any computerized data structure for storing the information in these tables may be used. For example, the value table described above is a specific example of a xe2x80x9cvalue storexe2x80x9d (i.e., it stores the data values representing the user-view values of information in the database); the instance table is a specific example of an xe2x80x9cinstance storexe2x80x9d and a xe2x80x9cconnectivity storexe2x80x9d (i.e., it both identifies instances of data items in the value store and represents relationships among instances of data items in the value store); and the displacement table is a specific example of a xe2x80x9ccardinality storexe2x80x9d (i.e., it represents the frequency of occurrence of equal instances of data values). The columns of a table are specific examples of a xe2x80x9clistxe2x80x9d or, more generally, a xe2x80x9cset.xe2x80x9d A xe2x80x9cset,xe2x80x9d for the purposes of the present invention, comprises one or more xe2x80x9celements,xe2x80x9d each having a value or values and a xe2x80x9cposition,xe2x80x9d where the position specifies the location of the element within the set. In the discussion above, a xe2x80x9ccellxe2x80x9d in a column of a table is an example of an xe2x80x9celementxe2x80x9d and its position in the set is its row number.
Furthermore, although the embodiments described herein refer to and manipulate traditional xe2x80x9crecordsxe2x80x9d, the invention is not limited to records and is generally applicable to represent relationships between data values.
All such variations are alternate embodiments of this invention.
Typical database operations supported by the database system of the present invention include, but are not limited to:
1) reconstructing physical records,
2) finding records matching query criteria,
3) joining tables in standard ways,
4) deleting and/or adding records,
5) modifying existing records, and
6) combinations of these and other standard database operations to perform useful tasks.
The present invention provides a new and efficient way of structuring databases enabling efficient query and update processing, reduced database storage requirements, and simplified database organization and maintenance. Rather than achieve orderedness through increasing redundancy (i.e., superimposing an ordered data representation on top of the original unordered representation of the same data), the present invention eliminates redundancy on a fundamental level. This reduces storage requirements, in turn enabling more data to be concurrently stored in RAM (enhancing application performance and reducing hardware costs) and speeds up transmission of databases across communication networks, making high-speed main-memory databases practical for a wide spectrum of business and scientific applications. Fast query processing is possible without the overhead found in a fully inverted database (such as excessive memory usage). Furthermore, with the data structures of the present invention, data is much more easily manipulated than in traditional databases, often requiring only that certain entries in the instance table be changed, with no copying of data. Database operations in general are thus more efficient using the present invention. In addition, certain operations such as histographic analysis, data compression, and multiple orderings, which are computationally intensive in record-oriented structures, are obtainable immediately from the structures described herein. The invention also provides improved processing in parallel computing environments.
The database system of the present invention can be used as a back-end for an efficient database compatible with almost any database front-end employing industry standard middleware (e.g., Microsoft""s Open Database Connectivity (ODBC) or Microsoft""s Active-X Data Objects (ADO)) and will provide almost drop-in compatibility with the large corpus of existing database software. Alternatively, a native stand-alone engine can be directly implemented, via, for example, C++ functions, templates and/or class libraries. Implemented either as a back-end to middleware or as a stand-alone engine, this invention provides a database that looks familiar to the user, but which is managed internally in a novel and efficient manner.
For certain data sets, space saving techniques can be applied in accordance with additional aspects of the present invention, as described herein. One such technique, referred to herein as xe2x80x9ccombined fieldsxe2x80x9d, is to combine low cardinality fields into a single column having values representing the various combinations of the original fields. While such combined fields may have value and displacement lists that are larger than the value and displacement lists of the uncombined columns taken together, overall space savings may result from the reduced number of columns needed in the instance and displacement tables. Searching for values matching the first part of such combined fields is generally unchanged, but searching for other parts is more complicated.
One technique in accordance with another aspect of the present invention for simplifying the searching of interior subfields of a combined field is to include all values in the Cartesian product of the original fields in the combined field and to sort the values in nested sort order. Preferably, each subfield value is assigned a number based on its position in the sort order of the subfield. This technique is referred to herein as xe2x80x9cmetric combined fields.xe2x80x9d Performing complex queries on such a field is extremely fast because no searching is requiredxe2x80x94values in a metric combined field representing subfields with specific values can be directly computed due to there being fixed distances between subfields with a given value. The computation can be additionally simplified by padding the cardinality of each subfield to a power of two, resulting in a metric combined field wherein each subfield""s value falls within a separate and distinct sequence of bits. In alternative embodiments, containerization techniques are used to reduce the size of the value and displacement lists required for representing the complete set of all possible values in a metric combined field, while preserving its metric property (i.e., regular spacing between like values).